题面

前言

一开始疯狂看不懂题意，然后就发现了神奇的东西 $Link$

$Ps:$ 题号 $3420$

解题思路

二分、树形DP

分析

显然，答案存在单调性，因此可以二分

二分之后就是如何

Code

#include<bits/stdc++.h>
#define rgt register
#define rint rgt int
#define LL long long
#define rLL rgt LL
#define inf 0x7f7f7f7f
#define N 300007
using namespace std;
template<class K>inline bool cmax(K&a,const K&b){return(a<b)?a=b,1:0;}
template<class K>inline bool cmin(K&a,const K&b){return(a>b)?a=b,1:0;}
int n,t,ver[N<<1],nxt[N<<1],head[N],ans,m,f[N];
inline int read() {
    rint s=0;
    rgt char c=getchar();
    while(!isdigit(c)) c=getchar();
    while(isdigit(c)) s=(s<<1)+(s<<3)+c-'0',c=getchar();
    return s;
}
inline void add(rint x,rint y) {
    ver[++t]=y,nxt[t]=head[x],head[x]=t,
    ver[++t]=x,nxt[t]=head[y],head[y]=t;
}
inline void dfs(rint k,rint fa) {
    rint i,to;
    for(i=head[k];i;i=nxt[i]) {
        to=ver[i];if(to==fa) continue;
        dfs(to,k),f[k]+=f[to]+1;
    }f[k]-=m,cmax(f[k],0);
}
int main()
{
    rint i,l,r;r=n=read(),l=0;
    for(i=1;i<n;i++) add(read(),read());
    while(l<=r) {
        memset(f,0,sizeof(f)),
        m=(l+r)>>1,dfs(1,0);
        if(!f[1]) ans=m,r=m-1;
        else l=m+1;
    }printf("%d",ans);
    return 0;
}

devil.